//
// Created by Administrator on 2021/5/10.
//
#include <string>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    string removeDuplicateLetters(string s) {
        // 贪心 + 单调栈
        vector<int> num(26, 0), inStack(26, 0);
        for (const auto &x:s) {
            ++num[x - 'a']; // 统计各个字符数量
        }
        string stack; // string可以实现栈的效果
        for (const auto &x:s) {
            if (!inStack[x - 'a']) { // 当前字符x未在栈中
                while (!stack.empty() and x < stack.back()) {  // 构造单调栈
                    if (num[stack.back() - 'a'] > 0) { // 被弹出的字母后面还有
                        inStack[stack.back() - 'a'] = 0;
                        stack.pop_back();
                    } else break;  // 栈顶字母是最后一个，不能弹出
                }
                // x 入栈
                stack.push_back(x);
                inStack[x - 'a'] = 1;  // 记录栈中元素
            }
            --num[x - 'a']; // 字母数量-1
        }
        return stack;
    }
};

int main() {
    Solution sol;
    cout << sol.removeDuplicateLetters("bcac") << endl;
    cout << sol.removeDuplicateLetters("cbacdcbc") << endl;
    return 0;
}